package 剑指offer;

public class 剑指Offer26树的子结构 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
//        TreeNode node5 = new TreeNode(3);
        node.left = node1;
        node.right = node2;
        node2.left = node3;
        node2.right = node4;

        System.out.println(isSame(node, node2));

    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null && B == null) return true;//如果传入得AB都为null，两树相等，直接返回true；
        if (A == null || B == null) return false;//如果传入得AB只有一个为null，范围fasle；
        //否则，先比较AB两棵树是否为同一颗树，在比较A得左右子树是否为和B为相同子树。
        return (isSame(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));

    }

    /**
     * 传入两个非空得树节点,就可以知道两棵树得是否为相同子树
     * @param A
     * @param B
     * @return
     */
    public static boolean isSame(TreeNode A,TreeNode B){
        if (B == null) return true;//如果在比较过程中，B从非空走到空，那么无论A是否为空，B一定是A得子树
        if (A == null && B != null) return false;//如果走到A为空，B不为空，那么B一定不是A得子树
        //否则比较A，B得val，和AB孩子得val。完全相同则为子树，有一个不同就为false；
        return (A.val == B.val && isSame(A.left,B.left) && isSame(A.right,B.right));
    }
}
